package airthmetic.exercise.dp;

// 经典dp的0-1背包问题
//1.1、问题描述
//      给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。
//      现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？
public class BackPack {
    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp(int[] wt, int[] v, int N, int W) {
        int[][] dp = new int[N+1][W+1];
        for(int i=0; i<N+1; i++){
            dp[i][0] = 0;
        }
        for(int j=0; j<W+1; j++){
            dp[0][j] = 0;
        }

        for(int i=1; i<=N; i++){
            for(int w=1; w<=W; w++){
                if(wt[i-1] > w){
                    dp[i][w] = dp[i-1][w];
                }else{
                    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - wt[i-1]]   + v[i-1]);
                }
            }
        }

        return dp[N][W];

    }


    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] wt = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack().dp(wt,v,N,W));
    }
}
